#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
using namespace std;


//class Solution {
//public:
//    int removeElement(vector<int>& nums, int val) {
//        int left = 0;
//        int right = nums.size() - 1;
//        while (left <= right)
//        {
//            if (nums[left] == val)
//            {
//                nums[left] = nums[right--];
//            }
//            else
//            {
//                left++;
//            }
//        }
//        return left;
//    }
//};
//
//
//int main()
//{
//    vector<int> v1 = { 0,1,2,2,3,0,4,2 };
//    Solution().removeElement(v1,2);
//    system("pause");
//}



//class Solution {
//public:
//    vector<int> sortedSquares(vector<int>& nums) {
//        for (size_t i = 0; i < nums.size(); i++)
//        {
//            nums[i] = nums[i] * nums[i];
//        }
//        sort(nums.begin(), nums.end());
//        return nums;
//    }
//};



//class Solution {
//public:
//    vector<int> sortedSquares(vector<int>& nums) {
//        vector<int> vv;
//        vv.resize(nums.size());
//
//        int left = 0;
//        int right = nums.size() - 1;
//        int k = nums.size() - 1;
//        while (left <= right)
//        {
//            int num1 = nums[left] * nums[left];
//            int num2 = nums[right] * nums[right];
//            if (num1 > num2)
//            {
//                vv[k] = num1;
//                k--;
//                left++;
//            }
//            else
//            {
//                vv[k] = num2;
//                k--;
//                right--;
//            }
//        }
//        return vv;
//    }
//};
//
//int main()
//{
//    vector<int> v1 = { -4,-1,0,3,10 };
//    Solution().sortedSquares(v1);
//    system("pause");
//}
//
//
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int result = INT_MAX;
//        int sum = 0;
//        int Sublen = 0;
//        int i = 0;
//        for (int j = 0; j < nums.size(); j++)
//        {
//            sum += nums[j];
//            while (sum >= target)
//            {
//                Sublen = j - i + 1;
//                result = fmin(result, Sublen);
//                sum -= nums[i];
//                i++;
//            }
//        }
//        return result == INT_MAX ? 0 : result;
//    }
//};


//
//class Solution {
//public:
//    string replaceSpace(string s) {
//        int count = 0;
//        int sOldSize = s.size() - 1;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == ' ')
//                count++;
//        }
//        int newcapicty = s.size() + (count * 2);
//        s.resize(newcapicty);
//        int newSize = s.size() - 1;
//        while (sOldSize != newSize)
//        {
//            if (s[sOldSize] != ' ')
//            {
//                s[newSize--] = s[sOldSize--];
//            }
//            else
//            {
//                s[newSize--] = '0';
//                s[newSize--] = '2';
//                s[newSize--] = '%';
//                sOldSize--;
//            }
//        }
//        return s;
//    }
//};


//
//class Solution {
//public:
//    void reverse(string& s, int left, int right)
//    {
//        while (left < right)
//        {
//            swap(s[left], s[right]);
//            left++;
//            right--;
//        }
//    }
//    string reverseWords(string s) {
//        int slow = 0;
//        for (size_t i = 0; i < s.size(); i++)
//        {
//            if (s[i] != ' ')
//            {
//                if (slow != 0)
//                    s[slow++] = ' ';
//                while (i < s.size() && s[i] != ' ')
//                {
//                    s[slow++] = s[i++];
//                }
//            }
//        }
//        s.resize(slow);
//
//        reverse(s, 0, s.size() - 1);
//        int start = 0;
//        for (size_t i = 0; i <= s.size(); i++)
//        {
//            if (s[i] == ' ' || i == s.size())
//            {
//                reverse(s, start, i - 1);
//                start = i + 1;
//            }
//        }
//        return s;
//    }
//};


//struct ListNode* reverseList(struct ListNode* head) {
//    if (!head)
//        return NULL;
//
//    struct ListNode* cur = head;
//    struct ListNode* prev = NULL;
//    while (cur != NULL)
//    {
//        struct ListNode* next = cur->next;
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//    }
//    return prev;
//}